/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2023-04-20
 * Time:14:55
 */

import java.util.List;

/**
 * BM12单链表的排序
 * 归并排序
 */

public class sortInList {
    public ListNode sortInList (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //快慢指针寻找中点
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        //分割链表
        ListNode right = sortInList(slow.next);
        slow.next = null;
        ListNode left = sortInList(head);

        ListNode dummy = new ListNode(0);
        ListNode tmp = dummy;

        //合并链表
        while (left != null && right != null){
            if (left.val > right.val){
                tmp.next = right;
                tmp = tmp.next;
                right = right.next;
            }else {
                tmp.next = left;
                tmp = tmp.next;
                left = left.next;
            }
        }
        //不一定刚搞好对称
        tmp.next = left ==null ? right : left;
        return dummy.next;
    }
}
